package sol.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Combination Sum III
 */
public class Issue216 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        find(1, k, n, new ArrayList<Integer>(), res);
        return res;
    }

    //从from开始，找k个数，和为target。找到之后与prefix组成一个结果放到res中
    private void find(int from, int k, int target, List<Integer> prefix, List<List<Integer>> res) {
        if (target == 0 && k == 0) {
            res.add(prefix);
            return;
        } else if (k == 0 || target < 0)
            return;
        else {
            for (int i = from; i <= 10 - k; ++i) {
                List<Integer> newPrefix = new ArrayList<Integer>(prefix);
                newPrefix.add(i);
                find(i + 1, k - 1, target - i, newPrefix, res);
            }
        }
    }


    public static void main(String[] args) {
        int n = 9;
        int k = 3;
        Issue216 sol = new Issue216();
        List<List<Integer>> res = sol.combinationSum3(k, n);
        for (List<Integer> r : res) {
            System.out.println(r);
        }
    }
}
